662. 二叉树最大宽度

Similar Question

leading to the advanced question

Solution Tips

关键就是父与子的索引关系

方案一: BFS

假设父节点的索引为 i, 那么子节点的索引为 left: 2^i, right: 2^i + 1

var widthOfBinaryTree = function(root) {
    // 父节点的 index 和子节点的 index 的关系?
    // 父节点为 i, 则左子节点为 2*i, 右子节点为 2*i + 1
    root.index = 0;
    const queue = [root];
    let maxWidth = 0;

    while (queue.length) {
        const n = queue.length;
        let firstNotNullIndex = -1;
        for (let i = 0; i < n; i++) {
            const node = queue.shift();
            if (node !== null) {
                if (firstNotNullIndex === -1) {
                    firstNotNullIndex = node.index;
                }
                else {
                    maxWidth = Math.max(maxWidth, node.index - firstNotNullIndex);
                }

                if (node.left) {
                    // index 有可能溢出, 如何安全计算呢? 虽然关心的是差值, 但是确实有可能就是溢出了
                    // 不能因为 case 是挨在一起的就针对性的处理
                    // 做法就是相对于第一个节点做差值, 这样只要单层节点不是溢出的, index 也不会溢出
                    node.left.index = 2 * node.index - firstNotNullIndex;
                    queue.push(node.left);
                }

                if (node.right) {
                    node.right.index = 2 * node.index + 1 - firstNotNullIndex;
                    queue.push(node.right);
                }
            }
        }
    }

    return maxWidth;
};

方案二: DFS

没办法一层层的比较,所以需要用哈希表记录 depth ,每次到了 depth 都去与这一层第一个遍历到的节点比较 index

超时方案: 错误思路

var widthOfBinaryTree = function(root) {
    // 层次遍历改版, 就算是 null 也得继续 push
    // 需要根据深度来判断是否要用 null 填充
    const queue = [root];
    let maxWidth = 0;

    while (queue.length) {
        const n = queue.length;
        let shouldPad = false;
        let firstNotNUll = -1;

        for (let i = 0; i < n; i++) {
            const node = queue.shift();
            if (node !== null) {
                // 只要其中一个不是 null, 下一行就需要用 null 填充
                shouldPad = true;
                queue.push(node.left);
                queue.push(node.right);
                if (firstNotNUll === -1) {
                    firstNotNUll = i;
                }
                else {
                    // 计算该层的最大宽度
                    maxWidth = Math.max(maxWidth, i - firstNotNUll);
                }
            }
            else if (shouldPad) {
                queue.push(null);
                queue.push(null);
            }
        }
    }

    // 超时了, 换思路, 贪心思想, 直接找到最左边的节点和最右边的节点? 不行, 考虑菱形的二叉树
    // 每次左就加1, 每次右也加1, 反过来就减1
    // 最右侧节点的索引: 2^n - 1 - ()
    // 最左侧节点的索引: 2^(n - d) - 1
    // 每次 left d++, 每次 right d--, 最小为 0

    return maxWidth;
};